#coding=utf-8 
'''
Created on 2012-10-28

@author: infear
'''
#http://blog.csdn.net/v_JULY_v/article/details/6313257
#假设有一颗二叉树，已知这棵树的节点上不均匀的分布了若干石头，石头数跟这棵二叉树的节点数相同，石头只可以在子节点和父节点之间进行搬运，每次只能搬运一颗石头。
#请问如何以最少的步骤将石头搬运均匀，使得每个节点上的石头上刚好为1。
class StoneNode():
    def __init__(self, _size, _value,_left, _right):
        self.size = _size
        self.right = _right
        self.left = _left
        self.value=_value

    
    def addStone(self):
            self.size = self.size + 1
    
    def removeStone(self):
            self.size = self.size - 1

    

def getTreeSize(n):
    if n is None:
        return 0
    else:
        return n.size+getTreeSize(n.left)+getTreeSize(n.right)

def getTreeScale(n):
    if n is None:
        return 0
    else:
        return 1+getTreeScale(n.left)+getTreeScale(n.right)
    
def _print(n):
    if n is None:
        pass
    else:
        print n.size,n.value
        _print(n.left)
        _print(n.right)


def func(root):
    if root is None:
        return 0
    else:
        steps = 0
        gap_left=getTreeSize(root.left)-getTreeScale(root.left)
        gap_right=getTreeSize(root.right)-getTreeScale(root.right)
        while gap_left != 0:
            steps=steps+1
            if gap_left < 0:
                gap_left = gap_left + 1
                root.left.addStone()
            else:
                gap_left = gap_left - 1
                root.left.removeStone()
        while gap_right != 0:
            steps=steps+1
            if gap_right < 0:
                gap_right = gap_right + 1
                root.right.addStone()
            else:
                gap_right = gap_right - 1
                root.right.removeStone()
        root.size=1  
        print "steps: ",steps
        return steps+func(root.left)+func(root.right)


        
n4=StoneNode(0,4,None,None)
n5=StoneNode(3,5,None,None)
n6=StoneNode(2,6,None,None)
n2=StoneNode(1,2,n4,n5)
n3=StoneNode(0,3,n6,None)
n1=StoneNode(0,1,n2,n3)
_print(n1)
print func(n1)
_print(n1)                
